package likou.tanxin;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/09/26 18:41
 */
public class _330 {
    public static void main(String[] args) {
        System.out.println(minPatches(new int[]{1,5,10},20));
    }
    public static int minPatches(int[] nums, int n) {
        int patches = 0, i = 0;
        long miss = 1; // 使用long避免整数溢出错误
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss){
                miss += nums[i++];
            } else { // patch miss to the array
                miss += miss;
                patches++; // increase the answer
            }
        }
        return patches;
    }
}
